//
// 中缀表达式的求值
// 难度：困难
//

#include <string>
#include <iostream>
#include "GStack.h"

// 符号优先级优雅表示，考试可以不写
enum Priority {
    Less,
    Equal,
    Greater
};

// 比较 first 符号和 second 符号的优先级
// 优先级高的符号不再符合栈先进后出的规则，需要特殊处理
Priority getPriority(char first, char second) {
    // 左括号和右括号的优先级相同
    if (first == '(' && second == ')') {
        return Equal;
    } // 加减的优先级低于乘除， 前左括号的优先级和后坐括号的优先级最低
    else if (first == '(' || second == '(' || (first == '+' || first == '-') && (second == '*' || second == '/')) {
        return Less;
    } // 其他情况前符号的优先级都高于后符号，因为从左到右计算
    else {
        return Greater;
    }
}

// 将中缀表达式转化为后缀表达式
// 后缀表达式在程序中更好求值
std::string convertExpression(std::string &input) {
    // res: 最终的后缀表达式
    // operators： 操作符栈
    std::string res;
    GStack<char> operators;
    for (char cur: input) {
        // 所有的中缀数字在后缀中顺序不变
        if (std::isdigit(cur)) {
            res.push_back(cur);
        } // 符号是后缀表达式的关键
        else {
            // 如果空栈，则无疑问入栈
            // 如果当前是左括号，直接入栈，并配合右括号特殊处理
            if (operators.empty() || cur == '(') {
                operators.push(cur);
            } // 遇到右括号，输出栈中所有符号，直到遇到左括号为止，弹出左括号
            else if (cur == ')') {
                while (operators.top() != '(') {
                    res.push_back(operators.top());
                    operators.pop();
                }
                operators.pop();
            } // 非括号的操作符统一处理，栈中的符号本来符合先进后出，也就是后面的数字先运算
                // 但如果前面的运算符优先级更高或相等，则不符合中序的算数规律，需要将栈前方所有高优先级的符号先运算
                // 直到遇到优先级低的符号或栈空为止
                // 此时当前符号及后面的符号才符合算数运算规律，入栈
            else {
                while (getPriority(operators.top(), cur) == Greater && !operators.empty()) {
                    res.push_back(operators.top());
                    operators.pop();
                }
                operators.push(cur);
            }
        }
    }

    // 将栈中剩余的符号输出
    while (!operators.empty()) {
        res.push_back(operators.top());
        operators.pop();
    }

    // 注意，栈中的符号永远是先运算后在运算前的，符合后缀规律的符号
    // 但是中缀表达式往往从左到右先运算前再运算后，所以需要提前出栈运算
    // 在主循环中，栈中的符号都是后面的运算更高的，符合的是后缀
    // 我们需要调整栈，使不符合规律的运算符号不再栈中

    return res;
}

[[maybe_unused]] void getExpressionValue() {
    std::string input;
    std::getline(std::cin, input);

    std::string res = convertExpression(input);

    for (char c: res) {
        std::cout << c << ' ';
    }
    std::cout << std::endl;
}
